#include "main/utils.h"
using namespace std;

vector<string> getNeighbors(string cur) {
  vector<string> ret;
  for (int i = 0; i < cur.size(); ++i) {
    string tmp = cur;
    tmp[i] = tmp[i] == '0' ? '9' : (char)(cur[i] - 1);
    ret.push_back(tmp);

    tmp = cur;
    tmp[i] = tmp[i] == '9' ? '0' : (char)(cur[i] + 1);
    ret.push_back(tmp);
  }
  return ret;
}

int openLock1(const string& target,
              const vector<string>& deadlist) {
  string init = "0000";
  set<string> visited(deadlist.begin(), deadlist.end());
  if (visited.find(init) != visited.end() ||
      visited.find(target) != visited.end()) {
    return -1;
  }
  queue<string> queue1, queue2;
  queue1.push(init);
  visited.insert(init);
  int length = 0;
  while (!queue1.empty()) {
    auto cur = queue1.front();
    queue1.pop();
    if (cur == target) {
      return length;
    }
    auto neighbors = getNeighbors(cur);
    for (auto neighbor : neighbors) {
      if (visited.find(neighbor) == visited.end()) {
        queue2.push(neighbor);
        visited.insert(neighbor);
      }
    }
    if (queue1.empty()) {
      ++length;
      swap(queue1, queue2);
    }
  }
  return -1;
}

int openLock2(const string& target,
              const vector<string>& deadlist) {
  string init = "0000";
  set<string> visited(deadlist.begin(), deadlist.end());
  if (visited.find(init) != visited.end() ||
      visited.find(target) != visited.end()) {
    return -1;
  }
  if (init == target) {
    return 0;
  }
  set<string> set1, set2;
  set1.insert(init);
  set2.insert(target);
  visited.insert(init);
  visited.insert(target);
  int length = 1;
  while (!set1.empty() && !set2.empty()) {
    if (set2.size() < set1.size()) {
      swap(set1, set2);
    }
    set<string> set3;
    for (auto str : set1) {
      auto neighbors = getNeighbors(str);
      for (auto neighbor : neighbors) {
        if (set2.find(neighbor) != set2.end()) {
          return length;
        }
        if (visited.find(neighbor) == visited.end()) {
          visited.insert(neighbor);
          set3.insert(neighbor);
        }
      }
    }
    ++length;
    set1 = set3;
  }
  return -1;
}

int main() {
  string target = "0202";
  vector<string> deadlist = {"0102", "0201"};
  cout << openLock1(target, deadlist) << endl;
  cout << openLock2(target, deadlist) << endl;

  return 0;
}
